﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace ns
{

    public class OtherQuestion : MonoBehaviour
    {

        //70. 爬楼梯
        //https://leetcode-cn.com/problems/climbing-stairs/
        //动态规划
        //注意结果溢出，f(x)=f(x−1)+f(x−2) 第X级阶梯=可能跨1步，可能跨2步，边界条件，滚动数组p\q\r  
        public int ClimbStairs(int n)
        {
            if (n < 3)
            {
                return n;
            }
            int dp1 = 1;
            int dp2 = 2;
            int dp = 0;
            for (int i = 3; i < n + 1; i++)
            {
                dp = dp1 + dp2;
                dp1 = dp2;
                dp2 = dp;
            }

            return dp;
        }

        //121. 买卖股票的最佳时机
        //https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
        //一次遍历法，价格最低点买入,找到另一个最高点
        //
        public int MaxProfit(int[] prices)
        {
            int minp = int.MaxValue;
            int maxp = 0;
            for (int i = 0; i < prices.Length; i++)
            {
                if (prices[i] < minp) //找到历史最低
                {
                    minp = prices[i];
                }
                else if (prices[i] - minp > maxp)
                {
                    maxp = prices[i] - minp;
                }
            }
            return maxp;
        }

        //198. 打家劫舍
        //https://leetcode-cn.com/problems/house-robber/
        //动态规划
        //
        public int Rob(int[] nums)
        {
            if (nums.Length == 0) return 0;
            if (nums.Length == 1) return nums[0];
            int[] dp = new int[nums.Length];
            dp[0] = nums[0]; //偷窃的金额数
            dp[1] = System.Math.Max(nums[0], nums[1]);

            for (int i = 2; i < nums.Length; i++)
            {
                dp[i] = System.Math.Max(dp[i - 2] + nums[i], dp[i - 1]);
            }

            return dp[nums.Length - 1];
        }
    }


    public class Solution
    {
        //384. 打乱数组
        //https://leetcode-cn.com/problems/shuffle-an-array/
        //
        //
        private int[] array;
        private int[] original;

        public Solution(int[] nums)
        {
            array = nums;
            original = nums.Clone() as int[];
        }
        /** Resets the array to its original configuration and return it. */
        public int[] Reset()
        {
            array = original;
            original = original.Clone() as int[];
            return array;
        }

        /** Returns a random shuffling of the array. */
        public int[] Shuffle()
        {
            for (int i = 0; i < array.Length; i++)
            {
                swapAt(i,randRange(i, array.Length));
            }
            return array;
        }

        private void swapAt(int i, int j)
        {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }

        System.Random rand = new System.Random();

        private int randRange(int min, int max)
        {
            return rand.Next(max - min) + min;
        }
    }


}